package base.Chapter02;

/**
 * 异或运算的性质
 * 无进位的加法: 相异得1, 相同得0
 * 性质1: 0^N = N
 * 性质2: N^N = 0
 * 性质3: 满足交换律, 结合律
 */
public class Code01_ExclusiveOR {
    // 性质1
    public static void test1() {
        int zero = 0;
        int some = 10;
        System.out.println(zero ^ some);
    }

    // 性质2
    public static void test2() {
        int a = 10;
        System.out.println(a ^ a);
    }

    // 性质3
    public static void test3() {
        int a = 10;
        int b = 20;
        System.out.println((a ^ b) == (b ^ a));
    }

    //性质3
    public static void test4() {
        int a = 10, b = 20, c = 30;
        System.out.println(((a ^ b) ^ c) == (a ^ (b ^ c)));
    }

    //性质应用: 不使用额外变量交换两个数
    public static void swapVariable(int num1, int num2) {
        System.out.println("交换前: Num1: " + num1 + " Num2: " + num2);
        num1 = num1 ^ num2;
        num2 = num1 ^ num2;
        num1 = num1 ^ num2;
        System.out.println("交换后: Num1: " + num1 + " Num2: " + num2);
    }

    //异或应用: 找出数组中出现了奇次数的元素 (数据要求: 只有一个出现了奇数次的元素)
    public static int findOddTimeElement(int[] arr) {
        // 数据合规校验: 1, 数组为null; 2, 数组元素个数为0; 3, 数组长度为偶数(肯定不是一个元素为奇数个)
        if (arr == null || arr.length < 1 || arr.length % 2 != 1) {
            throw new RuntimeException("数组数据不合法");
        }
        // 查找逻辑
        // 1, 如果有1个元素, 那么就是它了
        int exor = arr[0]; // 也可以初始化为0, 这样下面循环条件就少些一个判断条件.
        // 2, 如果有大于1个元素, 那么通过异或运算获取到指定元素
        for (int i = 1; arr.length > 1 && i < arr.length; i++) {
            exor ^= arr[i];
        }
        return exor;
    }

    // 异或应用: 找出int类型数中最右侧第一个不为1的位
    public static int findRightFirstOnePosition(int target) {
        return (~(target) + 1) & target;
    }

    // 异或应用: 找出数组中两个出现了奇数次的元素, 其余元素为偶数次
    public static void findTwoOddTimesElement(int[] arr) {
        if (arr == null || arr.length < 1) {
            throw new RuntimeException("数组数据不合法.");
        }
        // 1, 计算所有的元素的异或值, 得到exor

        int exor = 0;
        for (int element : arr) {
            exor ^= element;
        }
        // 2, 找出exor右边第一个不为0的数 only
        int only = (~(exor) + 1) & exor;
        // 3, 遍历arr, 然后分别于only做与运算, 得0的做与运算得到left
        int left = 0, right = 0;
        for (int element : arr) {
            if ((element & only) == 0) {
                left ^= element;
            }
        }
        //  4, left^exor得到right
        right = exor ^ left;
        System.out.println("A: " + left + " B: " + right);
    }

    // 异或面试题: 数组中有一种元素出现了K次, 其它数都出现了M次, M>1, K<M, 找出出现K次的数
    public static int findKTimesElement(int[] arr, int m, int k) {

        int[] sum = new int[32];
        // 算所有元素, 每个位上为1的总次数, 累加到sum数组中
        for (int element : arr) {
            for (int i = 0; i < 32; i++) {
                int onlyOne = 1 << i; // 向右移位指定次数
                if ((element & onlyOne) != 0) // 判断当前元素的当前位是否为1, 如果是1则加指定次数
                    sum[i]++;
            }
        }
        // 复原出现k次的数
        int result = 0;
        for (int i = 0; i < sum.length; i++) {
            if (sum[i] % m == k) { // 说明目标元素该位是1
                int onlyOne = 1 << i;
                result |= onlyOne;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5};
        //findTwoOddTimesElement(arr);
        int result = findKTimesElement(arr, 3, 2);
        System.out.println(result);
    }
}
